
/*
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef LMG_H
#define LMG_H 1

/* A splay-tree datatype.
   Copyright (C) 1998 Free Software Foundation, Inc.
   Contributed by Mark Mitchell (mark@markmitchell.com).

This file is part of GNU CC.

GNU CC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU CC is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

/* For an easily readable description of splay-trees, see:

     Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
     Algorithms.  Harper-Collins, Inc.  1991.

   The major feature of splay trees is that all basic tree operations
   are amortized O(log n) time for a tree with n nodes.  */

/* lmgsplay.c */

/* Use typedefs for the key and data types to facilitate changing
   these types, if necessary.  These types should be sufficiently wide
   that any pointer or scalar can be cast to these types, and then
   cast back, without loss of precision.  */
typedef unsigned long int lmgsplay_tree_key;
typedef unsigned long int lmgsplay_tree_value;

/* Forward declaration for a node in the tree.  */
typedef struct lmgsplay_tree_node *lmgsplay_tree_node;

/* The type of a function which compares two lmgsplay-tree keys.  The
   function should return values as for qsort.  */
typedef int (*lmgsplay_tree_compare_fn) (lmgsplay_tree_key,
					 lmgsplay_tree_key);

/* The type of a function used to deallocate any resources associated
   with the key.  */
typedef void (*lmgsplay_tree_delete_key_fn) (lmgsplay_tree_key);

/* The type of a function used to deallocate any resources associated
   with the value.  */
typedef void (*lmgsplay_tree_delete_value_fn) (lmgsplay_tree_value);

/* The type of a function used to iterate over the tree.  */
typedef int (*lmgsplay_tree_foreach_fn) (lmgsplay_tree_node, void *);

/* The nodes in the lmgsplay tree.  */
struct lmgsplay_tree_node
{
  /* The key.  */
  lmgsplay_tree_key key;

  /* The value.  */
  lmgsplay_tree_value value;

  /* The left and right children, respectively.  */
  lmgsplay_tree_node left;
  lmgsplay_tree_node right;
};

/* The lmgsplay tree itself.  */
typedef struct lmgsplay_tree
{
  /* The root of the tree.  */
  lmgsplay_tree_node root;

  /* The comparision function.  */
  lmgsplay_tree_compare_fn comp;

  /* The deallocate-key function.  NULL if no cleanup is necessary.  */
  lmgsplay_tree_delete_key_fn delete_key;

  /* The deallocate-value function.  NULL if no cleanup is necessary.  */
  lmgsplay_tree_delete_value_fn delete_value;
} *lmgsplay_tree;

extern lmgsplay_tree lmgsplay_tree_new (lmgsplay_tree_compare_fn,
					lmgsplay_tree_delete_key_fn,
					lmgsplay_tree_delete_value_fn);
extern void lmgsplay_tree_delete (lmgsplay_tree);
extern void lmgsplay_tree_insert (lmgsplay_tree,
				  lmgsplay_tree_key, lmgsplay_tree_value);
extern lmgsplay_tree_node lmgsplay_tree_lookup
  (lmgsplay_tree, lmgsplay_tree_key);
extern int lmgsplay_tree_foreach (lmgsplay_tree,
				  lmgsplay_tree_foreach_fn, void *);
extern int lmgsplay_tree_compare_ints (lmgsplay_tree_key, lmgsplay_tree_key);
extern int lmgsplay_tree_compare_pointers (lmgsplay_tree_key,
					   lmgsplay_tree_key);
extern int
lmgsplay_tree_compare_strings (lmgsplay_tree_key k1, lmgsplay_tree_key k2);

/* lmgdfs.c */
extern void lmg_dfs (void);

/* lmgmem.c */
extern void *lmg_malloc (size_t n);
extern void lmg_free (void *ptr);

/* lmgself.c */
extern void lmg_selfedges (void);

/* lmgconn.c */
extern void lmg_connect (void);
extern void lmg_connectclear (void);

/* lmgcycles.c */
extern void lmg_cycles (void);

/* lmgsplit.c */
extern void lmg_splitedges (void);

/* lmgne.c */
extern void lmg_nodelistadd (struct lmgnode *node);
extern void lmg_nodelistclear (void);
extern void lmg_edgelistadd (struct lmgnode *from, struct lmgnode *to,
			     int color, int style);
extern void lmg_edgelistclear (void);
extern struct lmgnodel *lmg_dummynode (void);
extern struct lmgedgel *lmg_addedge2 (struct lmgnode *from,
				      struct lmgnode *to);
extern void lmg_deledge (struct lmgedgel *el);

/* lmglevel.c */
extern void lmg_levels (void);
extern void lmg_levelsclear (void);
extern int lmg_nnal (int level);

/* lmgbary.c */
extern void lmg_barycenter (void);
extern void lmg_barycenterclear (void);
extern unsigned int lmg_crossings (void);

/* lmginout.c */
extern void lmg_inout (void);

/* lmguniqn.c */
extern struct lmgnode *lmg_uniqn (char *name);
extern void lmg_uniqnadd (char *name, struct lmgnode *node);
extern void lmg_uniqnclear (void);

/* lmguniqs.c */
extern char *lmg_uniqs (char *s);
extern void lmg_uniqsclear (void);

/* lmgvar.c */
extern struct lmgnodel *lmgnodelist;
extern struct lmgnodel *lmgnodelistend;
extern struct lmgedgel *lmgedgelist;
extern struct lmgedgel *lmgedgelistend;
extern int lmgmaxlevel;
extern int lmgnlevels;
extern struct lmgnodel **lmglevels;
extern int *lmgnal;
extern int lmgdebug;
extern int lmgmalloccount;
extern int lmgfreecount;
extern int lmgnrealnodes;
extern int lmgnrealedges;
extern int lmgnsingles;
extern int lmgedgelabelcount;
extern lmgsplay_tree lmgstrings;
extern lmgsplay_tree lmgnodes;

#endif

/* End */
